/**
 * 73. Set Matrix Zeroes 矩阵置零
 * https://leetcode.com/problems/set-matrix-zeroes/
 */
class SetMatrixZeroes {
    /**
     * 方法：将矩阵中元素为0的行和列全部置为0
     * 
     * Args:
     *     matrix: 二维整数矩阵
     * 
     * Returns:
     *     void: 直接修改输入矩阵
     * 
     * Time: O(m*n) 其中m是矩阵行数，n是矩阵列数
     * Space: O(1) 使用常数空间
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0){
                flagCol0 = true;
            }
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for(int i = m - 1; i >= 0; i--){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
            if(flagCol0){
                matrix[i][0] = 0;
            }
        }
        
    }
}